package com.julius.design.suanfa.dynamic;

/**
 * @author julius
 * @date 2021-10-29 下午 2:28
 * <p>
 *      礼物的最大价值
 *      在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
 *      给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
 *      (0 ,0)-------------------------->(m ,n)
 *      https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/
 * </p>
 */
public class GiftMaxCost {


    /**
     * 礼物的最大价值
     * 输入:
     * [
     *   [1,3,6,1],
     *   [4,4,3,1],
     *   [1,2,1,1]
     * ]
     *      1  4  10 11
     *      5  9  13 14
     *      6  11 14 15
     *
     *
     * 输出: 15
     * 解释: 路径 1→3→6→3→1→1 可以拿到最多价值的礼物
     * 向右或者向下  i++  j++  也是所有的情况是看先i++还是先j++
     * 动态规划分析：
     *      状态定义：
     *          二维数组的db数组也要是二维数组dp[][]
     *          dp[i][j] 代表着到达该位置的最大价值
     *          dp[i-1][j] 代表到达该位置上方位置的最大价值
     *          dp[i][j-1] 代表到达该位置左侧位置的最大价值
     *
     *      状态转移方程：
     *           dp[i][j] = max(dp[i-1][j],dp[i][j-1])+gird[i][j]
     *      初始值：
     *          dp[0][0] = gird[0][0]
     *      返回值：
     *          dp[i][j]
     *
     * @param gird
     * @return
     */
    public static int maxValue(int[][] gird){
        //行数
        int m = gird.length;
        //列数
        int n = gird[0].length;

        int[][] dp = new int[m][n];
        dp[0][0] = gird[0][0];
        for (int i = 0;i< m ;i++){
            for (int j = 0 ;j< n;j++){
                if(i == 0 && j == 0){
                    continue;
                }
                int up = 0,left = 0;
                if(j != 0){
                    left = dp[i][j-1];
                }
                if(i != 0){
                    up = dp[i-1][j];
                }
                int max = Math.max(up,left);
                dp[i][j] = gird[i][j] + max;
            }
        }
        return dp[m-1][n-1];
    }


    public static void main(String[] args) {
        int[][] gird = new int[][]{{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(maxValue(gird));
    }
}
